﻿using System;
using System.Collections.Generic;

namespace QuickSort.ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 3, 4, 3, 2, 2, 4, 9, 6, 3 };
            Console.WriteLine("before:");
            for(int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i]+" ");
            }
            Console.WriteLine("");
            DateTime StartTime = DateTime.Now;
            QuickSort(arr, 0, arr.Length);
            DateTime EndTime = DateTime.Now;
            TimeSpan ts = EndTime - StartTime;
            Console.WriteLine("after:");
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");
            }
            Console.WriteLine("");
            Console.WriteLine("耗时:" + ts);
            Console.ReadLine();
        }
        /// <summary>
        /// 全部快速排序算法
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="low"></param>
        /// <param name="high"></param>
        static void QuickSort(int[] arr,int low,int high)
        {

            int pos;
            if (low < high)
            {
                pos = OnceQuickSort(arr, low, high-1);
                OnceQuickSort(arr, low, pos - 1);
                OnceQuickSort(arr, pos + 1, high-1);
            }
        }
        /// <summary>
        /// 单次快速排序算法
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="low"></param>
        /// <param name="high"></param>
        /// <returns></returns>
        static int OnceQuickSort(int[] arr,int low,int high)
        {
            int x = arr[low];
            while (low < high)
            {
                while (low < high && arr[high] >= x)
                    high--;
                if (low < high)
                {
                    arr[low] = arr[high];
                    low++;
                }
                while (low < high && arr[low] < x)
                    low++;
                if (low < high)
                {
                    arr[high] = arr[low];
                    high--;
                }
            }
            arr[low] = x;
            return low;
        }
    }
}